import java.util.Scanner;

//递归: 方法自己调用自己的过程 实现递归 需要去推导出 一个递推公式
//前提: 有一个趋近于终止的条件
public class demo {
    //青蛙跳台阶问题(提示, 使用递归)一只青蛙一次可以跳上 1 级台阶，
    //也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法
    //类似于斐波那契 还可以使用循环迭代的方法
    public static int fun8(int n){
        if(n == 1 || n == 2){
            return n;
        }
        else
            return fun8(n - 1) + fun8(n - 2);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fun8(n));
    }










    //迭代 这样减少计算 提高效率
    public static int fun7(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 1;
        for (int i = 3; i <= n; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;

    }
    public static void main8(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fun7(n));
    }

    //递归 斐波那契 这种写法重复计算的数据太多 认识给的数很大 结果出来很比较慢 所以可以使用循环(迭代)
    public static int fun6(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        else
            return fun6(n - 1) + fun6(n - 2);
    }
    public static void main7(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fun6(n));
    }









    //递归 输入一个非负整数返 回组成它的数字之和 例如输入1729则应该返回1+7+2+9
    public static int fun5(int n){
        if (n != 0)
        return n % 10 + fun5(n / 10);
        else
            return 0;
    }
    public static void main6(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fun5(n));
    }












    //按顺序打印数字的每一位
    public static void fun4(int n){
        if (n != 0){
            fun4(n / 10);
            System.out.print(n % 10 + " ");
        }
    }
    public static void main5(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        fun4(n);
    }









    //递归求n的和
    public static int fun3(int n){
        if (n == 1)
            return 1;
        return n+fun3(n - 1);
    }
    public static void main4(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fun3(n));
    }








    //递归n的阶乘
    public static int fun2(int n){
        if (n == 1)
            return 1;
        else
            return fun2(n-1)*n;
    }
    public static void main3(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fun2(n));
    }







    //简单递归
    public static void fun1(int n){
        if(n == 1)
            return;
        fun1(n - 1);
        n--;
    }
    public static void main2(String[] args) {
        int n = 3;
        fun1(n);
    }











    public static void fun(){
        fun();
        //在main调用fun()会出现Exception in thread "main" java.lang.
        // StackOverflowError 表示栈溢出 终止条件错误或没有终止条件
    }
    public static void main1(String[] args) {
        fun();
    }
}
